Shareware Grab Bag/Shareware Grab Bag.iso/050/madtrb10.arc/GRAPH.PAS

Pascal/Delphi Source File | 1985-12-16 | 35.8 KB | 704 lines

Program GraphTheory;

{ *************************************************************************** }
{ *                                                                         * }
{ *                        GRAPH THEORY PROGRAM                             * }
{ *                             Program #2                                  * }
{ *                                                                         * }
{ *                     Class: CS 367     Section: 4                        * }
{ *                         Instructor: Wiegand                             * }
{ *                                                                         * }
{ *                       Written by Chris Maeder                           * }
{ *                Edited and Compiled using Turbo Pascal                   * }
{ *                            on an IBM PC                                 * }
{ *                                                                         * }
{ *   DEFINITION:                                                           * }
{ *        A graph can be thought of as a two dimensional structure         * }
{ *        which consists of nodes (or vertices) connected by a set of      * }
{ *        edges (or arcs).                                                 * }
{ *                                                                         * }
{ *                         o----------o                                    * }
{ *                          edge^     |                                    * }
{ *                                    |                                    * }
{ *                                    |                                    * }
{ *                                    |                                    * }
{ *                                    |                                    * }
{ *                                    o------------o                       * }
{ *                                   /             ^node                   * }
{ *                                 /                                       * }
{ *                               /                                         * }
{ *                             /                                           * }
{ *                           o                                             * }
{ *                                                                         * }
{ *        This graph structure can be represented in computer memory       * }
{ *        as a two dimensional array (see Procedure LinkMatrixModule).     * }
{ *        By performing a sequential union test for each element in the    * }
{ *        matrix, we are then able to determine the minimum pathlength     * }
{ *        between two nodes.                                               * }
{ *                                                                         * }
{ *   PURPOSE:                                                              * }
{ *        1. Print report heading.                                         * }
{ *        2. Read input data file.                                         * }
{ *        3. Echo print the input data file.                               * }
{ *        4. Check that the linked nodes and the node queries are          * }
{ *           contained in the initial node list.  Print an error           * }
{ *           message if any discrepencies are found.                       * }
{ *        5. Using a boolean adjacency matrix, determine minimum           * }
{ *           pathlengths between query nodes.                              * }
{ *        6. Print pathlength results.                                     * }
{ *                                                                         * }
{ *   INPUT:                                                                * }
{ *        1. Node data that is stored on a disk file. For specification    * }
{ *           of input data see Procedure InputModule.                      * }
{ *                                                                         * }
{ *   OUTPUT:                                                               * }
{ *        1. Print output heading                                          * }
{ *        2. Echo print the input data file as it is read in               * }
{ *           a. Order                                                      * }
{ *              i.   Initial list of nodes                                 * }
{ *              ii.  List of linked nodes                                  * }
{ *              iii. List of pathlenth queries                             * }
{ *           b. Format                                                     * }
{ *              i.   Use list identifier headers                           * }
{ *              ii.  Print error message for any nodes not contained       * }
{ *                   in the initial node list                              * }
{ *        3. Print minimum pathlength results                              * }
{ *           a. Identify both of the query's nodes                         * }
{ *           b. State the minimum pathlength                               * }
{ *           c. Identify any query nodes that have no path between         * }
{ *              each other.                                                * }
{ *                                                                         * }
{ *   ALGORITHM:                                                            * }
{ *        See Procedure PathLengthModule                                   * }
{ *                                                                         * }
{ *************************************************************************** }

Const
  MAX_NODES=15;                              { maximum number of independant nodes }
  MAX_STRING_SIZE=24;
  NODE_LIST_MKR='ZZZ';                       { a marker delineating the the initial node list and the  linked node list }
  NODE_EDGE_MKR='ZZZ ZZZ';                   { a marker delineating the linked node list and the query list }
  FILE_NAME='Graph.Fil';
  DEBUG_INPUT_MODULE=False;                  { a toggle used for debugging the input module }
  DEBUG_LINK_MODULE=False;                   { a toggle used for debugging the link module }
  DEBUG_PATHLENGTH_MODULE=False;             { a toggle used for debugging the pathlength module }
  L_PRINT=False;                             { a boolean used to redirect output to the printer }

Type
  NodeEntry=String[MAX_STRING_SIZE];
  AdjacencyMatrix=Array[1..MAX_NODES,1..MAX_NODES] Of Boolean;
  Index=Array[1..MAX_NODES] Of NodeEntry;    { a index list used to store file entries }
  NodeRange=1..MAX_NODES;
  QueryRecord=
    Record
      QueryNode1:String[12];                 { string used to store query node 1 }
      CorrespondingInitialNode1:NodeRange;   { linked list that links the query nodes to the initial nodes }
      QueryNode2:String[12];                 { string used to store query node 1 }
      CorrespondingInitialNode2:NodeRange;   { linked list that links the query nodes to the initial nodes }
      QueryPathLength:0..MAX_NODES;          { used to store the computed pathlength for the query entry }
    End; { QueryRecord }

Var
  InitialAdjacencyMatrix:AdjacencyMatrix;    { this adjacency matrix stores all the edges between adjacent nodes }
  Nodes:Index;                               { this is an index of all nodes that tells us what are the proper
                                               rows and cols of the adjacency matrix}
  EdgedNodes:Index;                          { this a list of edged nodes }
  Query:Array[1..MAX_NODES] Of QueryRecord;  { this is a query list }
  MaxNumOfNodes:Integer;                     { total number of nodes }
  MaxNumOfEdgedNodes:Integer;                { total number of adjacent nodes }
  MaxNumOfQueries:Integer;                   { total number of queries }
  HoldPtr:Integer;                           { a temporary pointer used in the re-directing of output from the
                                               screen to the printer }



Procedure InitializeAdjacencyMatrix(Var AdjacencyMatrixName:AdjacencyMatrix);

{ This procedure initializes the passed adjacency matrix so that all the elements within the adjacency matrix
  are set to False.  This corresponds to no single edge occuring between adjacency matrix nodes. }

Var
  Row,Col:Integer;

Begin   { InitializeAdjacencyMatrix }
  For Row:=1 To MAX_NODES Do
    For Col:=1 To MAX_NODES Do
      AdjacencyMatrixName[Row,Col]:=False;
End;    { InitializeAdjacencyMatrix }



Function FirstNodeEntry(IndexEntry:NodeEntry):NodeEntry;

{ This function is passed an index entry which contains the names of two nodes in the given graph.
  These node names are seperated by a single blank space in the index entry.  This function picks off
  the first node name and passes this node name back. }

Begin   { FirstNodeEntry }
  FirstNodeEntry:=Copy(IndexEntry,1,(Pos(' ',IndexEntry)-1));
End;    { FirstNodeEntry }



Function SecondNodeEntry(IndexEntry:NodeEntry):NodeEntry;

{ This function is passed an index entry which contains the names of two nodes in the given graph.
  These node names are seperated by a single blank space in the index entry.  This function picks off
  the second node name and passes this node name back. }

Begin   { SecondNodeEntry }
  SecondNodeEntry:=Copy(IndexEntry,(Pos(' ',IndexEntry)+1),(Length(IndexEntry)-Pos(' ',IndexEntry)));
End;    { SecondNodeEntry }



Procedure PrintHeading;

{ This procedure prints a heading for the output. }

Begin   { PrintHeading }
  WriteLn;
  WriteLn('GRAPH THEORY DEMONSTRATION PROGRAM');
  WriteLn;
  WriteLn;
End;    { PrintHeading }



Procedure PrintAdjacencyMatrix(AdjacencyMatrixName:AdjacencyMatrix);

{ This procedure prints out the elements of the passed adjacency matrix. }

Var
  Row,Col:Integer;

Begin   { PrintAdjacencyMatrix }
  WriteLn;
  WriteLn('Row   Column');
  WriteLn;
  Write('    ');
  For Col:=1 To MaxNumOfNodes Do             { print out header of column numbers }
    Write(Col,'   ');
  For Row:=1 To MaxNumOfNodes Do             { routine prints out matrix entries }
    Begin
      WriteLn;
      Write(Row,'   ');                      { print out row number }
      For Col:=1 To MaxNumOfNodes Do
        If AdjacencyMatrixName[Row,Col]=True Then
          Write('T   ')
        Else
          Write('F   ');
    End; { For Row }
  WriteLn;
End;    { PrintAdjacencyMatrix }



Procedure InputModule;

{ *************************************************************************** }
{ *                                                                         * }
{ *   This module controls the reading of entries out of the file named     * }
{ *   above and stores the entries into their proper indexes.               * }
{ *                                                                         * }
{ *   The input file data is organized as follows:                          * }
{ *                                                                         * }
{ *     A list of Node names                   Node_Name_1                  * }
{ *     that exist on the graph                Node_Name_2                  * }
{ *                                                .                        * }
{ *                                                .                        * }
{ *                                            Node_Name_N                  * }
{ *                                                                         * }
{ *     A marker used in seperating the data   ZZZ                          * }
{ *                                                                         * }
{ *     A list of node name pairs              Node_Name Node_Name          * }
{ *     that are adjacent to                   Node_Name Node_Name          * }
{ *     each other                                 .                        * }
{ *                                                .                        * }
{ *                                            Node_Name Node_Name          * }
{ *                                                                         * }
{ *     A marker used in seperating the data   ZZZ ZZZ                      * }
{ *                                                                         * }
{ *     A query list of node name pairs        Node_Name Node_Name          * }
{ *     This program is to determine           Node_Name Node_Name          * }
{ *     The path length between the pairs          .                        * }
{ *                                                .                        * }
{ *                                            Node_Name Node_Name          * }
{ *                                                                         * }
{ *************************************************************************** }

Var
  FileEntry:NodeEntry;
  AdjacencyMatrixFile:Text;                  { text file }



    Procedure PrintIllegalEntry(Entry:NodeEntry);

    { This procedure prints out an error message to the user that the current index entry contains at least one node name
      that does not correspond to any of the node names that were initially read into the node name list. }

    Begin   { PrintIllegalEntry }
      WriteLn;
      WriteLn('   The following data entry was found to have at least one node name ');
      WriteLn('   that was not found in the initial data list.');
      WriteLn;
      WriteLn('          Illegal Data Entry= ',Entry);
      WriteLn;
    End;    { PrintIllegalEntry }



    Function LegalEntry(IndexEntry:NodeEntry):Boolean;

    { The passed index entry contains the names of two nodes.  This function determines if
      the two names are 'Legal', that is, both names are contained in the previously given
      data set of node names. }

    Var
      NodeOne,NodeTwo:NodeEntry;             { string variables used to retain the individual node names that
                                               are contained in the index array. }
      IndexRow:Integer;
      NodeOneLegal,NodeTwoLegal:Boolean;     { boolean flag that is used to tell if individual node entry is legal }

    Begin   { LegalEntry }
      NodeOneLegal:=False;                   { initialize boolean flag }
      NodeTwoLegal:=False;                   { initialize boolean flag }
      NodeOne:=FirstNodeEntry(IndexEntry);
      NodeTwo:=SecondNodeEntry(IndexEntry);
      For IndexRow:=1 To MaxNumOfNodes Do
        Begin
          If NodeOne=Nodes[IndexRow] Then
            NodeOneLegal:=True;
          If NodeTwo=Nodes[IndexRow] Then
            NodeTwoLegal:=True;
        End; { For IndexRow }
      LegalEntry:=(NodeOneLegal And NodeTwoLegal And (NodeOne<>NodeTwo)) Or (NodeOne='ZZZ');
    End;    { LegalEntry }



    Procedure InsertLegalEntry(QueryEntry:NodeEntry);

    { This procedure places the legal query into the query record so that the two node names are seperated
      and a linked list corresponding to the query node and initial node is established.  This allows us to
      see if an adjacency has been established later on. }

    Var
      IndexRow:Integer;

    Begin   { InsertLegalEntry }
      With Query[MaxNumOfQueries] Do
        Begin
          QueryNode1:=FirstNodeEntry(QueryEntry);    { insert first query name into query record }
          QueryNode2:=SecondNodeEntry(QueryEntry);   { insert second query name into query record }
          For IndexRow:=1 To MaxNumOfNodes Do        { Routine links the query node names with the initial node names }
            Begin                                    { with an index value.  This allows us to easily acess the }
              If QueryNode1=Nodes[IndexRow] Then     { particular element of the transformed matrix to see if adjacency }
                CorrespondingInitialNode1:=IndexRow; { has just occured. }
              If QueryNode2=Nodes[IndexRow] Then
                CorrespondingInitialNode2:=IndexRow;
            End; { For IndexRow }
          QueryPathLength:=0;                        { Initialize query pathlength. A '0' denotes no path yet established. }
        End; { With Query }
    End;    { InsertLegalEntry }



Begin   { InputModule }
  If DEBUG_INPUT_MODULE Then
    Begin
      WriteLn;
      WriteLn('***INPUT MODULE***');
    End;
  MaxNumOfNodes:=0;
  MaxNumOfEdgedNodes:=0;
  MaxNumOfQueries:=0;
  Assign(AdjacencyMatrixFile,FILE_NAME);     { assign to a disk file }
  Reset(AdjacencyMatrixFile);                { open the file for reading }
  WriteLn;
  WriteLn;
  WriteLn('INITIAL LIST OF NODES:');
  WriteLn;
  WriteLn;
  Repeat                                     { read in the list of nodes }
    ReadLn(AdjacencyMatrixFile,FileEntry);   { read node entry out of file }
    If FileEntry<>NODE_LIST_MKR Then
      Begin
        MaxNumOfNodes:=MaxNumOfNodes+1;
        Nodes[MaxNumOfNodes]:=FileEntry;
        WriteLn('   ',FileEntry);            { echo out node entry }
      End; { If FileEntry }
  Until FileEntry=NODE_LIST_MKR;
  WriteLn;
  WriteLn;
  WriteLn('LIST OF LINKED NODES:');
  WriteLn;
  WriteLn;
  Repeat                                     { read in list of edged nodes }
    ReadLn(AdjacencyMatrixFile,FileEntry);   { read linked node entry out of file }
    If LegalEntry(FileEntry) Then            { determine if the file entry's names are contained in the initial node list}
      Begin
        If FileEntry<>NODE_EDGE_MKR Then
          Begin
            MaxNumOfEdgedNodes:=MaxNumOfEdgedNodes+1;
            EdgedNodes[MaxNumOfEdgedNodes]:=FileEntry;
            WriteLn('   ',FileEntry);        { echo out legal linked node entry }
          End; { If FileEntry }
      End
    Else
      PrintIllegalEntry(FileEntry);
  Until FileEntry=NODE_EDGE_MKR;
  WriteLn;
  WriteLn;
  WriteLn('LIST OF PATH LENGTH QUERIES:');
  WriteLn;
  WriteLn;
  Repeat                                     { read in list of queires }
    ReadLn(AdjacencyMatrixFile,FileEntry);   { read query entry out of file }
    If LegalEntry(FileEntry) Then            { determine if the file entry's names are contained in the initial node list}
      Begin
        MaxNumOfQueries:=MaxNumOfQueries+1;
        InsertLegalEntry(FileEntry);
        WriteLn('   ',FileEntry);            { echo out legal query entry }
      End
    Else
      PrintIllegalEntry(FileEntry);
  Until Eof(AdjacencyMatrixFile);
  Close(AdjacencyMatrixFile);                { Close the disk file }
  If DEBUG_INPUT_MODULE Then
    Begin
      WriteLn;WriteLn('InitialAdjacencyMatrix follows:');
      PrintAdjacencyMatrix(InitialAdjacencyMatrix);
    End;
End;    { InputModule }



Procedure LinkMatrixModule;

{ *************************************************************************** }
{ *                                                                         * }
{ *    This module sets up the intial adjacency matrix which is called      * }
{ *    InitialAdjacencyMatrix.  The elements of this adjacency matrix       * }
{ *    correspond to whether there exists a single edge between adjacent    * }
{ *    nodes, i.e.                                                          * }
{ *                                                                         * }
{ *       True (T) in a element denotes that there is an edge of length     * }
{ *                one between adjacent nodes.                              * }
{ *       False (F) in a element denotes that there is not an edge of one   * }
{ *                between nodes.                                           * }
{ *                                                                         * }
{ *    The rows and columns of the adjacency matrix structure correspond    * }
{ *    to the given list of nodes.  The example below uses cities as nodes  * }
{ *    of a graph                                                           * }
{ *                                                                         * }
{ *                              C   M   M                                  * }
{ *                              h   a   i                                  * }
{ *                              i   d   l                                  * }
{ *                              c   i   w                                  * }
{ *                              a   s   a                                  * }
{ *                              g   o   u                                  * }
{ *                              o   n   k                                  * }
{ *                                      e                                  * }
{ *                                      e                                  * }
{ *                                                                         * }
{ *                  Chicago     F   F   T                                  * }
{ *                                                                         * }
{ *                  Madison     F   F   T                                  * }
{ *                                                                         * }
{ *                  Milwaukee   T   T   F                                  * }
{ *                                                                         * }
{ *    Note that the major diagonal elements are all false since an         * }
{ *    element cannot have an adjacent edge to itself.  Notice also that    * }
{ *    all adjacency matrix entries are symmetric about the major           * }
{ *    diagonal.  One final note, the InitialAdjacencyMatrix never gets     * }
{ *    altered during the run of the program since it is needed in          * }
{ *    determining the shortest distance between two nodes for every query. * }
{ *                                                                         * }
{ *************************************************************************** }

Var
  IndexRow:Integer;      { A pointer to the current row of the index EdgedNodes }
  Row,Col:Integer;
  Test:Boolean;



    Function ConnectingEdgeExists(IndexEntry,NodeOne,NodeTwo:NodeEntry):Boolean;

    { This function is passed two node names from the given graph which are contained in IndexEntry.  This function is
      used in a sequential manner to determine if adjacency exists for the element corresponding to the edge of the
      nodes of the initial adjacency matrix. }

    Begin   { ConnectingEdgeExists }
      If DEBUG_LINK_MODULE Then
        Begin
          WriteLn;
          WriteLn('Function: ConnectingEdgeExists');
          WriteLn;
          WriteLn('  InitialNodesIndex,Node1= ',NodeOne);
          WriteLn('  InitialNodesIndex,Node2= ',NodeTwo);
          WriteLn('  EdgedNodesIndex,Node1=  ',FirstNodeEntry(IndexEntry));
          WriteLn('  EdgedNodesIndex,Node2=  ',SecondNodeEntry(IndexEntry));
          WriteLn;
          If (((NodeOne=FirstNodeEntry(IndexEntry))And
            (NodeTwo=SecondNodeEntry(IndexEntry)))Or
            ((NodeOne=SecondNodeEntry(IndexEntry))And
            (NodeTwo=FirstNodeEntry(IndexEntry)))) Then
              WriteLn('  Connecting Edge Exists')
          Else
            WriteLn('  Connecting Edge Does Not Exist');
        End;
      ConnectingEdgeExists:=(((NodeOne=FirstNodeEntry(IndexEntry))And
        (NodeTwo=SecondNodeEntry(IndexEntry)))Or
        ((NodeOne=SecondNodeEntry(IndexEntry))And
        (NodeTwo=FirstNodeEntry(IndexEntry))));
    End;    { ConnectingEdgeExists }



Begin   { LinkMatrixModule }
  If DEBUG_LINK_MODULE Then
    Begin
      WriteLn;
      WriteLn('***LINK MODULE***');
    End;
  For IndexRow:=1 To MaxNumOfEdgedNodes Do
    For Row:=1 To MaxNumOfNodes Do
      For Col:=1 To MaxNumOfNodes Do
        Begin
          If DEBUG_LINK_MODULE Then
            Begin
              WriteLn;
              WriteLn('  EdgedNodesIndexRow= ',IndexRow);
              WriteLn('  InitialAdjacencyMatrixRow=      ',Row);
              WriteLn('  InitialAdjacencyMatrixCol=      ',Col);
            End;
          If ConnectingEdgeExists(EdgedNodes[IndexRow],Nodes[Row],Nodes[Col]) Then
            InitialAdjacencyMatrix[Row,Col]:=True;
        End; { For Col }
  If DEBUG_LINK_MODULE Then
    Begin
      WriteLn;WriteLn('LinkedInitialAdjacencyMatrix follows:');
      PrintAdjacencyMatrix(InitialAdjacencyMatrix);
    End;
End;    { LinkMatrixModule }



Procedure PathLengthModule;

{ *************************************************************************** }
{ *                                                                         * }
{ *   This module controls the procedures used in determining the minimum   * }
{ *   path length (distance) between two nodes.  This module gets a list    * }
{ *   of path length queries from an array of records.                      * }
{ *                                                                         * }
{ *   These query nodes are checked with the transformed adjacency matrix   * }
{ *   to see if adjacency has occured.  If adjacency has occured then the   * }
{ *   pathlength is entered into that query's pathlength record field.      * }
{ *   If no adjacency was discovered in that transformation, then the       * }
{ *   query pathlength field remains zero (corresponding to no pathlength   * }
{ *   found).  The process is then repeated until all the pathlengths are   * }
{ *   found or the maximum number of transformations have occured.  The     * }
{ *   pathlength results are then printed.                                  * }
{ *                                                                         * }
{ *   The largest minimum pathlength between two nodes is equal to          * }
{ *                                                                         * }
{ *                    MaxPathLength=MaxNumOfNodes-1                        * }
{ *                                                                         * }
{ *   The maximum number of transformations of the adjacency matrix is      * }
{ *   equal to                                                              * }
{ *                                                                         * }
{ *                                 =MaxPathLength-1                        * }
{ *                                                                         * }
{ *   This is because we initially check for adjacency (pathlength=1)       * }
{ *   before any transformations occur.                                     * }
{ *                                                                         * }
{ *   For adjacency matrix transformation algorithm see Procedure           * }
{ *   TransformAdjacencyMatrix.                                             * }
{ *                                                                         * }
{ *************************************************************************** }

Var
  CurrentQuery:Integer;                      { a marker to the current query regord }
  PathLength:Integer;
  TestAdjacencyMatrix:AdjacencyMatrix;       { This matrix undergoes a transformation while determining minimum
                                               path lengths.  This matrix is used to determine the minimum pathlengths
                                               between two nodes.  Minimum pathlength is represented as a boolean 'TRUE'
                                               for the adjacency element corresponding to node1 and node2. }
  ContinueSearch:Boolean;                    { a boolean used to flag that there are still query pathlengths that
                                               have yet to be determined. }
  MaxPathLength:Integer;                     { largest minimum pathlength between two nodes }



    Procedure PrintQueryHeading;

    { This procedure prints the output heading for the minimum path length output
      to follow. }

    Begin   { PrintQueryHeading }
      WriteLn;
      WriteLn;
      WriteLn('MINIMUM PATH LENGTHS FOLLOW:');
      WriteLn;
      WriteLn;
    End;    { PrintQueryHeading }



    Procedure PrintPathLengthResults;

    { This procedure prints out the current query and the minimum path length between the two nodes being quered.
      The pathlength is stored in the Query record field 'QueryPathLength'.  This field can have a value from 0 to
      MAX_PATH_LENGTH.  A zero in the field denotes that no path has yet been established between the two nodes. }

    Var
      CurrentQuery:Integer;                  { a marker to the current query record }

    Begin   { PrintPathLengthResults }
      WriteLn;
      For CurrentQuery:=1 To MaxNumOfQueries Do
        With Query[CurrentQuery] Do
          If QueryPathLength=0 Then
            WriteLn('   No path exists between ',QueryNode1,' and ',QueryNode2)
          Else
            WriteLn('   The minimum pathlength between ',QueryNode1,' and ',QueryNode2,' is ',QueryPathLength);
    End;   { PrintPathLengthResults }



    Procedure CheckForAdjacency;

    { This procedure first determines if adjacency has just occurred for any of the queries from the query list.
      It does this by scanning for adjacency for those elements of the transformed matrix corresponding to the
      query nodes (whose pathlengths have not yet been established).  If adjacency is established in a query element,
      the query pathlength is set equal to the current pathlength.  If all the query's pathlengths have been determined,
      it returns a boolean to tell the calling search routine that all the pathlengths have been determined and
      can now exit the search routine and print results. }

    Var
      CurrentQuery:Integer;                  { a marker to the current query record }
      SearchDone:Boolean;                    { a boolean flag used to tell when all the pathlengths for all the
                                               queries have been determined. }

    Begin  { ContinueSearch }
      SearchDone:=True;
      For CurrentQuery:=1 To MaxNumOfQueries Do
        With Query[CurrentQuery] Do
          Begin
            If QueryPathLength=0 Then
              If TestAdjacencyMatrix[CorrespondingInitialNode1,CorrespondingInitialNode2]=True Then { test for adjacency }
                QueryPathLength:=PathLength  { set pathlength for query }
              Else
                SearchDone:=False;           { still pathlengths that need to be determined }
            If DEBUG_PATHLENGTH_MODULE Then
              Begin
                WriteLn;
                WriteLn('Current Query = ',CurrentQuery);
                WriteLn('PathLength    = ',PathLength);
                WriteLn('MatrixRow     = ',CorrespondingInitialNode1,'    MatrixCol     = ',CorrespondingInitialNode2);
                WriteLn('Matrix Value  = ',TestAdjacencyMatrix[CorrespondingInitialNode1,CorrespondingInitialNode2]);
              End;
          End; { With Query }
      ContinueSearch:=Not(SearchDone);       { return boolean }
    End;   { ContinueSearch }



    Procedure TransformTestAdjacencyMatrix;

    { This procedure transforms the TestAdjacenyMatrix.  The TestAdjacencyMatrix is the adjacency matrix
      that undergoes transformation.  The InitialAdjacencyMatrix remains as itself, being used as such in
      the matrix transformation routine.

      TempAdjacencyMAtrix is used to temporarily store the adjacency matrix as it undergoes transformation.
      This is so that the TestAdjacencyMatris can remain independant as the processproceeds.  After the
      transformation process is completed the TeatAdjacencyMatrix is equated to the TempAdjacencyMatrix.
      Then the TestAdjacencyMAtrix is checked if adjacency has occured for a particular query.

      Transformation Algorithm:
           Each element of the TestAdjacencyMatrix must be transformed, one at a time.
           What follows is how the transformation of one of these elements take place.

           Using the columns of the InitialAdjacencyMatrix and the rows of the TestAdjacencyMatrix corresponding
           to an elemt of the TestAdjacencyMatrix We will then transform that element.  We use the elements of the
           columns and rows sequentally, checking for union between the two column and row elements.  If any union exists
           then that corresponding element of the TempAdjacencyMatrix is set to true.

                                           To n
                TestAdjacencyMatrix(i,j) =  Or [InitialAdjacencyMatrix(k,i) And TestAdjacencyMatrix(j,l)]
                                           For k,l=1

           After the entire transformation is completed then the TestAdjacencyMatrix is equated to the now
           transformed matrix. }

    Var
      TempAdjacencyMatrix:AdjacencyMatrix;   { Temporary storage matrix for the matrix undergoing transformation
                                               ( so the old version of the TestAdjacencyMatrix remains independent
                                               of the new version of the TestAdjacencyMatrix as it becomes transformed).
                                               Adjacency is represented as a boolean 'TRUE' for TestAdjacencyMatrix
                                               element corresponding to the two queried nodes. }
      Row:Integer;                           { Row of the TestAdjacencyMatrix being used in the
                                               matrix transformation }
      Col:Integer;                           { Col of the InitialAdjacencyMatrix being used in the
                                               matrix transformation }
      Element:Integer;                       { That particular element in Row or Col that is used in a
                                               sequential manner in the matrix transformation }

    Begin   { TransformTestAdjacencyMatrix }
      PathLength:=PathLength+1;              { increment pathlength counter }
      For Row:=1 To MaxNumOfNodes Do
        For Col:=1 To MaxNumOfNodes Do
          Begin
            TempAdjacencyMatrix[Row,Col]:=TestAdjacencyMatrix[Row,1] And InitialAdjacencyMatrix[1,Col];
            For Element:=2 To MaxNumOfNodes Do
              TempAdjacencyMatrix[Row,Col]:=TempAdjacencyMatrix[Row,Col] Or (TestAdjacencyMatrix[Row,Element] And
                                            InitialAdjacencyMatrix[Element,Col]);
          End; { For Col }
      TestAdjacencyMatrix:=TempAdjacencyMatrix;
      If DEBUG_PATHLENGTH_MODULE Then
        Begin
          WriteLn;
          WriteLn('Transformed Matrix # ',PathLength);
          PrintAdjacencyMatrix(TestAdjacencyMatrix);
        End;
    End;    { TransformTestAdjacencyMatrix }



Begin { PathLengthModule }
  If DEBUG_PATHLENGTH_MODULE Then
    Begin
      WriteLn;
      WriteLn('***PATHLENGTH MODULE***');
    End;
  MaxPathLength:=MaxNumOfNodes-1;            { largest minimum pathlength between two nodes }
  PathLength:=1;                             { initialize the pathlength }
  ContinueSearch:=True;                      { initialize boolean flag }
  TestAdjacencyMatrix:=InitialAdjacencyMatrix;
  CheckForAdjacency;
  While ContinueSearch And (PathLength<MaxPathLength) Do { routine to search for query's pathlengths }
    Begin
      TransformTestAdjacencyMatrix;
      CheckForAdjacency;
    End;
  PrintQueryHeading;
  PrintPathLengthResults;
End;  { PathLengthModule }



Begin { Main Program }
  HoldPtr:=ConOutPtr;                        { temporaly store current output device address }
  If L_PRINT Then
    ConOutPtr:=LstOutPtr;                    { re-direct output to the printer }
  InitializeAdjacencyMatrix(InitialAdjacencyMatrix);
  PrintHeading;
  InputModule;
  LinkMatrixModule;
  PathLengthModule;
  ConOutPtr:=HoldPtr;                        { reset output device address }
End.  { Main Program }